class Node:
    con = []
    def __init__(self,x,y,cat):
        self.x = x
        self.y = y
        self.cat = cat
        self.con = []
        self.g = 0
        self.h = 0
        self.camefrom = 0
      

def NodeList(lab):
    graph = []
    for y in range(len(lab)):
        for x in range(len(lab[y])):
         if(lab[y][x]) > 0:
            graph.append(Node(x,y,lab[y][x]))
    return graph


def CheckCon(graph):
    dict = {}
    for Node in graph:
        dict[(Node.x,Node.y)] = Node
    for Node in graph:
        if (Node.x + 1, Node.y) in dict.keys():
            Node.con.append(dict[(Node.x + 1, Node.y)])
        if (Node.x - 1, Node.y) in dict.keys():
            Node.con.append(dict[(Node.x - 1, Node.y)])
        if (Node.x, Node.y + 1) in dict.keys():
            Node.con.append(dict[(Node.x, Node.y + 1)])
        if (Node.x, Node.y - 1) in dict.keys():
            Node.con.append(dict[(Node.x, Node.y - 1)])
 

def start(graph):
    for Node in graph:
        if Node.cat == 2:
            first = Node
    return first

def goaltest(s):
    return s.cat == 3

def goaltestN(s):
        return s.cat == 3 and s.x == 6 and s.y == 0

def select_best(frontier):
    currentMin = frontier[0]
    for element in frontier:
        if currentMin.g + currentMin.h > element.g + element.h:
            currentMin = element
    return currentMin
    
        
       

#Task b.
def Dsearch(graph):
    print("Depth Search")
    frontier = [start(graph)]
    explored = []
    while frontier != []:
        s = frontier.pop(0)
        print(s.x,s.y)  
        if goaltest(s):
            print("Explored nodes:", len(explored))
            return True
        for i in s.con:
            if i not in explored:
                frontier.insert(0,i)
        explored.append(s)
    

#Task c.
def Bsearch(graph):
    print("Breadth Search")
    frontier = [start(graph)]
    explored = []
    while frontier != []:
        s = frontier.pop(0)
        print(s.x,s.y)  
        if goaltest(s):
            print("Explored nodes:", len(explored))
            return True
        for i in s.con:
            if i not in explored:
                frontier.append(i)
        explored.append(s)
    
def heuristic(node):
    return (6 - node.x) + node.y

def reconGraph(sNode,eNode):
    path = []
    path.append(eNode)
    magic=eNode
    while sNode not in path:
        path.insert(0,magic.camefrom)
        magic=magic.camefrom
    for i in path:
        print(i.x, i.y)
        
    

#Task d.
def Asearch(graph):
    print("A* search")
    frontier = [start(graph)]
    explored = []
    while frontier != []:
        node = select_best(frontier)
        if goaltestN(node):
            reconGraph(start(graph),node)
            return True #did stuff
        frontier.remove(node)
        explored.append(node)
        for next in node.con:
            if next in explored:
                if node.g + 1 < next.g:
                    explored.remove(next)
                    frontier.append(next)
                    next.g = node.g + 1
                    next.h = heuristic(next)
                    next.camefrom = node
            elif next in frontier:
               if node.g + 1 < next.g:
                    next.g = node.g + 1
                    next.h = heuristic(next)
                    next.camefrom = node
            else:
                frontier.append(next)
                next.g = node.g + 1
                next.h = heuristic(next)
                next.camefrom = node
            




lab = [[0,0,0,0,0,0,3,0], 
[0,1,0,1,1,1,1,0], 
[0,1,1,1,0,1,0,0], 
[0,1,0,0,0,0,0,0], 
[0,1,1,0,1,1,1,0], 
[0,0,1,1,1,0,0,0], 
[0,1,1,0,1,1,1,3], 
[0,2,0,0,0,0,0,0]]    

NL = NodeList(lab)  
CheckCon(NL)
Dsearch(NL)
print("\n")
Bsearch(NL)
print("\n")
Asearch(NL)